package 链表;

/**
 * https://leetcode-cn.com/problems/middle-of-the-linked-list/
 */
public class _876_链表的中间结点 {
    public ListNode middleNode(ListNode head) {
        int size = 0;
        ListNode newHead = head;
        while (newHead != null) {
            newHead = newHead.next;
            size++;
        }
        size = size / 2;
        for (int i = 0; i < size; i++) {
            head = head.next;
        }
        return head;
    }

    /**
     * 快慢指针
     * 在同一位置,快指针走两步,慢指针走一步
     * 快指针的路程是慢指针的2倍
     */
    public ListNode middleNode1(ListNode head) {
        ListNode fast, last;
        fast = last = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            last = last.next;
        }
        return last;
    }
}
